package util

type Deque struct {
	size int
	head *node
	tail *node
}

type node struct {
	data interface{}
	pre  *node
	next *node
}

func (q *Deque) Size() int {
	return q.size
}

func (q *Deque) AddFirst(data interface{}) {
	q.size += 1
	n := &node{
		data: data,
		next: q.head,
	}

	if q.size == 1 {
		q.head = n
		q.tail = n
	} else {
		q.head.pre = n
		q.head = n
	}
}

func (q *Deque) AddLast(data interface{}) {
	q.size += 1
	n := &node{
		data: data,
		pre:  q.tail,
	}

	if q.size == 1 {
		q.head = n
		q.tail = n
	} else {
		q.tail.next = n
		q.tail = n
	}
}

func (q *Deque) RemoveFirst() interface{} {
	if q.size == 0 {
		return nil
	}
	n := q.head

	if q.size == 1 {
		q.head = nil
		q.tail = nil
	} else {
		q.head = q.head.next
		q.head.pre = nil
	}

	q.size -= 1
	n.next = nil

	return n.data
}

func (q *Deque) RemoveLast() interface{} {
	if q.size == 0 {
		return nil
	}
	n := q.tail

	if q.size == 1 {
		q.head = nil
		q.tail = nil
	} else {
		q.tail = q.tail.pre
		q.tail.next = nil
	}

	q.size -= 1
	n.pre = nil

	return n.data
}

func NewDeque() *Deque {
	return &Deque{}
}
